學習資源

https://labuladong.online/algo/data-structure-basic/hash-set/

學習記錄

今天是學習的第 16 天，主要學習了哈希集合的原理及程式碼實現：

哈希集合簡單來說就是對哈希表的再次封裝，實作原理是：

• 哈希表儲存鍵值對 key-value
• 哈希集合只關心鍵 key，忽略值

因此哈希集合的 API 可以直接複用哈希表的 API 來實現。

哈希集合元理

哈希集合的主要使用場景是「去重」，也就是不會出現重複的元素。

class MyHashSet {
    constructor() {
        // 這邊用的是 JavaScript 底層的 Map，用來儲存集合元素
        this.map = new Map();
    }

	// 增：向哈希集合中添加元素，複雜度 O(1)
    add(key) {
        // 向哈希表添加一個鍵值對，值用 true 作為佔位符
        this.map.set(key, true);
    }

	// 刪：從哈希集合中移除一個元素，複雜度 O(1)
    remove(key) {
        // 從哈希表中移除 key
        this.map.delete(key);
    }

	// 查：判斷元素是否存在，複雜度 O(1)
    contains(key) {
        // 判斷哈希表中是否包含 key
        return this.map.has(key);
    }
}

與哈希表的比較

學習總結

• 哈希集合就是對哈希表的再次封裝
• 操作哈希集合，就是操作哈希表的鍵
• 哈希集合的主要使用場景是 「去重」